Міністерство освіти і науки України Національний університет “Львівська політехніка” Звіт про виконання лабораторної роботи №3 На тему: „ Алгоритм шифрування DES” З курсу: “Методи і засоби криптологічних перетворень” Львів 2008 Мета: дослідити симетричні шифри на прикладі алгоритму DES. Теоретичні відомості Стандарт шифрування даних (англійською Data Encryption Standard — DES) був розроблений у 70-х роках фахівцями з IBM і у 1976 році був прийнятий через NBS та ANSI у якості федерального стандарту Сполучених Штатів для захисту комерційної та урядової інформації, не пов’язаної з національною безпекою. Цим актом увінчався цілий етап у розвитку криптографії — майже одночасно з’явилися принципово нові криптосистеми з відкритим ключем, яким присвячено більшість подальших розділів цієї книжки. Спробуємо простежити уявний шлях від шифру одноразового блокноту до криптосистеми DES. Для цього нагадаємо дві основні харак3К3стики першого. З одного боку, шифр одноразового блокноту є абсолютно надійним, а з іншого, він далеко не завжди є практичним через велику довжину ключа. Тому перший крок є таким — довжина ключа має бути фіксованою, а шифрування має відбуватися блоками. Як і шифр одноразового блокноту, DES оперує з інформацією поданою у двійковій формі, а довжина блоку і довжина ключа вибрані рівними 64. Іншими словами, двійкове повідомлення М розбивають на блоки по 64 біти і шифрують кожен блок окремо, використовуючи один і той же двійковий ключ К довжини 64. Таким чином, повідомлення М = М1М2М3 … перетворюється у криптотекст С = С1С2С3…, де d — ЕK(Мi). У стандарті DES кожен блок криптотексту Сi також є двійковою послідовністю довжини 64. Звернемося до питання вибору алгоритму Е. Апріорно він повинен задовольняти три умови: можливість дешифрування: для будь-якого ключа K різним блокам повідомлення М’ і М» відповідають різні блоки криптотексту ЕK(М’) і ЕK(М»), інакше кажучи, алгоритм ЕK з будь-яким ключем здійснює перестановку двійкових послідовностей довжини 64; ефективність: і шифрування, і дешифрування відбуваються швидко; надійність: якщо ключ невідомий, то немає способу розкриття шифру. Останній пункт потребує принципового уточнення. Зрозуміло, що як би вдало алгоритм Е не був спроектований, надійність, що давалася шифром одноразового блокноту, вже буде недосяжною. Недосяжною з тої причини, що будь-який блоковий шифр можна зламати за допомогою брутальної атаки, яка у нашому випадку полягає в переборі всіх двійкових ключів К довжини 64. Про яку ж надійність йдеться? Зауважимо, що всього двійкових ключів довжини 64 є 264. Елементарні обчислення показують, що комп’ютер із тактовою частотою 100 MHz перебиратиме всі можливі ключі 264/108 секунд, тобто довше ніж 5800 років. Звичайно, повний перебір необхідний лише у найгіршому випадку. У середньому, потрібний ключ буде знайдено вдвічі швидше — приблизно за 2900 років — час, за який таємниця втратить актуальність. Якщо для шифру невідомо методу його ламання упродовж більш реалістичного терміну, то такий шифр вважають надійним в обчислювальному сенсі. Якщо ми хочемо отримати криптосистему надійну у такому новому розумінні, зразу відмовимось від наївної спроби вдосконалити шифр одноразового блокноту і покласти ЕK(Мi) = Мi,K. Таке шифрування є дуже швидке, але вкрай ненадійне. Для розкриття досить просумувати за модулем 2 криптотекст із самим собою, але зсунутим на 64 позиції. Із рівності КК=0 випливає, що результат буде тим же, що й при сумуванні повідомлення із самим собою зсунутим на ту ж кількість позицій. Із цієї інформації, яка вже ніяк не залежить від ключа, неважко отримати саме повідомлення, запорукою чого є феномен надлишковості будь-якої природної мови. Розробники стандарту DES пропонують наступну конструкцію (подальший опис алгоритму спрощено задля акцентування найважливіших фаз його роботи). Алгоритм E приймає на вхід двійковий блок М довжини 64 та використовує ключ К, з якого виділяються 16 частин K1,…,K16 по 48 бітів кожна. Це так звані циклові клю...